package boggle;



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

/* 
 java implementation of cs106 lexicon class
 three methods implemented: containsWord, 
 containsPrefix, add
 1st Version, ljl, 2013.11.24
 Under GPL license, enjoy! 
*/

public class lexicon  implements Iterable<String> {
	private ArrayList<String> sortedWords;  // words are sorted!
	
	/**
	 * Construct the lexicon using filename
	 * @param filename: file name for the lexicon
	 */
	
	public lexicon(String filename) {
		sortedWords = new ArrayList<String>(); 
		BufferedReader br;
		try {
			InputStream configStream = getClass().getResourceAsStream(filename);
			br = new BufferedReader(new InputStreamReader(configStream));
							
			while (true) {
				String line = br.readLine();  // one word, one line
				if (line == null) break;
				sortedWords.add(line.trim().toLowerCase());
			}
			Collections.sort(sortedWords);
			br.close();
		} catch (IOException e) {
			System.out.println("Error reading file!");
			e.printStackTrace();
		}
				
	}
	
	public lexicon() {
		this("./ospd.txt");
	}
	/**
	 * add word to lexicon
	 * @param word: word to add
	 */
	
	public void add(String word) {
		sortedWords.add(word.toLowerCase());
		Collections.sort(sortedWords);
	}
	
	/**
	 * determine whether a word contains in lexicon
	 * @param word:  the word
	 * @return if true, then lexicon contains the word
	 * if false, no.
	 */
	public boolean containsWord(String word) {
		return bsearchWord(sortedWords,word.toLowerCase(), 0, sortedWords.size() - 1);
	}
	
	/**
	 * determine whether a prefix contains in lexicon
	 * @param prefix:  the prefix
	 * @return if true, then lexicon contains the word
	 * if false, no.
	 */
	
	public boolean containsPrefix(String prefix) {
		return bsearchPrefix(sortedWords,prefix.toLowerCase(), 0, sortedWords.size() - 1);
	}
	
	
	/**
	 * find word in sorted words list using binary search algorithm 
	 * @param words : Sorted word list 
	 * @param prefix :the prefix to find
	 * @param left :left index 
	 * @param right :right index 
	 * @return true if found, otherwise false
	 */
	
	private boolean bsearchPrefix(ArrayList<String> words,
			String prefix, int left, int right) {
		if (right < left)
			return false;
		int mid = left + (right - left) / 2;
		
		String midWord = words.get(mid);
		int comp = prefix.compareTo(midWord);
		if (midWord.indexOf(prefix) == 0)   // if prefix found in midWord
			return true;
		else if (comp < 0)
			return bsearchPrefix(words, prefix, left, mid - 1);
		else
			return bsearchPrefix(words, prefix, mid + 1, right);
	}

	/**
	 * find word in sorted words list using binary search algorithm 
	 * @param words : Sorted word list 
	 * @param word :the word to find
	 * @param left :left index 
	 * @param right :right index 
	 * @return true if found, otherwise false
	 */
	private boolean bsearchWord(ArrayList<String> words, String word, int left, int right) {
		if (right < left)
			return false;
		int mid = left + (right - left) / 2;
			
		int comp = word.compareTo(words.get(mid));
		
		if (comp == 0)
			return true;
		else if (comp < 0)
			return bsearchWord(words, word, left, mid - 1);
		else
			return bsearchWord(words, word, mid + 1, right);
	}

	
	
	
	@Override
	public Iterator<String> iterator() {
		return sortedWords.iterator();
	}

	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// unit test
		lexicon lex = new lexicon();
		
		//for(String word : lex) {
		//	System.out.println(word);
		//}
		
		if (lex.containsPrefix("tion"))
			System.out.println("found prefix tion");
		else 
			System.out.println("Not found!!");

	}

	
	
}
